import functools
class Solution(object):
    def minPushBox(self, grid):
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'S':
                    user = (i, j)
                if grid[i][j] == 'B':
                    box = (i, j)
                if grid[i][j] == 'T':
                    target = (i, j)
        @functools.cache
        def find_user_state(user, box):
            min_t = user
            already = {user}
            st = [user]
            while st:
                x, y = st.pop()
                for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                    if 0 <= ux < m and 0 <= uy < n and (ux, uy) not in already:
                        if grid[ux][uy] != '#' and (ux, uy) != box:
                            already.add((ux, uy))
                            st.append((ux, uy))
            return min(already), already
        def find_next_box(user, box):
            user, user_possible = find_user_state(user, box)
            x, y = box
            next_box_set = set()
            if (x - 1, y) in user_possible:
                if 0 <= x + 1 < m and grid[x + 1][y] != '#':
                    next_box = (x + 1, y)
                    next_user = find_user_state((x - 1, y), next_box)[0]
                    next_box_set.add((next_user, next_box))
            if (x + 1, y) in user_possible:
                if 0 <= x - 1 < m and grid[x - 1][y] != '#':
                    next_box = (x - 1, y)
                    next_user = find_user_state((x + 1, y), next_box)[0]
                    next_box_set.add((next_user, next_box))
            if (x, y - 1) in user_possible:
                if 0 <= y + 1 < n and grid[x][y + 1] != '#':
                    next_box = (x, y + 1)
                    next_user = find_user_state((x, y - 1), next_box)[0]
                    next_box_set.add((next_user, next_box))                
            if (x, y + 1) in user_possible:
                if 0 <= y - 1 < n and grid[x][y - 1] != '#':
                    next_box = (x, y - 1)
                    next_user = find_user_state((x, y + 1), next_box)[0]
                    next_box_set.add((next_user, next_box))
            return next_box_set
        st = {(user, box)}
        already = {(user, box)}
        dist = 0
        while st:
            print(st)
            next_st = set()
            for user, box in st:
                if box == target:
                    return dist
                else:
                    next_box_set = find_next_box(user, box)
                    for item in next_box_set:
                        if item not in already:
                            already.add(item)
                            next_st.add(item)
            st = next_st
            dist += 1
        return -1
    
data = Solution()
grid = [["#","#","#","#","#","#"],["#","T","#","#","#","#"],["#",".",".","B",".","#"],["#",".","#","#",".","#"],["#",".",".",".","S","#"],["#","#","#","#","#","#"]]
print(data.minPushBox(grid))